package Leetcode;

import base.ListNode;

import java.util.HashSet;

/**
 * 给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
 */
public class 力扣142_环形链表II {
    public static void main(String[] args) {
        ListNode a = new ListNode(1);
        ListNode b = new ListNode(2);
        ListNode c = new ListNode(3);
        ListNode d = new ListNode(4);
        ListNode e = new ListNode(5);
        a.next = b;
        b.next = c;
        c.next = d;
        d.next = e;
        e.next = b;

        ListNode listNode = detectCycle(a);
        System.out.println(listNode.val);
    }

    static ListNode detectCycle(ListNode head) {
        HashSet<ListNode> set = new HashSet<>();
        while (head != null && head.next != null) {
            set.add(head);
            if (set.contains(head.next)) {
                return head.next;
            }
            head = head.next;
        }
        return null;
    }
}
